class Solution
{
public:
    int kthGrammar(int n, int k)
    {
        if (n == 1)
        {
            return 0;
        }
        int prevK = (k + 1) / 2;
        int prev = kthGrammar(n - 1, prevK);
        if ((k & 1) && prev == 0)
        {
            return 0;
        }
        else if ((k & 1) && prev == 1)
        {
            return 1;
        }
        else if (prev == 0)
        {
            return 1;
        }
        else
        {
            return 0;
        }
    }
};